home *** CD-ROM | disk | FTP | other *** search
/ Deutsche Edition 1 / Deutsche Edition 1.iso / amok / 031-040 / amok32 / patterns / patterns.dok < prev    next >
Text File  |  1993-11-04  |  6KB  |  150 lines
  1. ======================================================================
  2. Dokumentation zu "Patterns" Version 1.1
  3. Autor: Nicolas Benezan, Postwiesenstr. 2, D7000 Stuttgart 60
  4. ======================================================================
  5.  
  6.  
  7. Übersicht
  8. ­­­­­­­­­
  9. * Kopierrecht
  10. * Umfang des Projekts
  11. * Beschreibung
  12. * Demo- / Testprogramm
  13.  
  14.  
  15. Kopierrecht
  16. ­­­­­­­­­­­
  17. Das komplette Projekt (Quelltext, Dokumentation und Objectcode) ist
  18. Public Domain Software. Es darf beliebig kopiert und verbreitet werden
  19. solange...
  20.  
  21. * mein Name und dieser Kopierrechtshinweis erhalten bleiben,
  22. * die Vollständigkeit des ganzen Projekts gewährleistet ist, und
  23. * mit dem Vertrieb dieser Software kein Gewinn erwirtschaftet wird.
  24.  
  25. Die Kommerzielle Nutzung ohne meine ausdrückliche schriftliche
  26. Genehmigung ist untersagt (über Gewinnbeteiligung läßt sich reden).
  27. W i c h t i g: Dies gilt insbesondere auch für "schwarze Schafe" der
  28. "PD"-Versandhäuser, die ganz offensichtlich Gewinn machen, was z.B. durch
  29. ganzseitige Anzeigen in Zeitschiften erkennbar ist.
  30.  
  31. Verbesserungsvorschläge sind stets willkommen. Falls Sie Veränderungen
  32. am Programm vornehmen, dokumentieren Sie diese bitte gut verständlich.
  33. Es würde mich freuen, wenn Sie mich über größere Veränderungen oder
  34. Erweiterungen in Kenntnis setzen würden.
  35.  
  36. (c) 1988 by Nicolas Benezan.
  37.  
  38.  
  39. Umfang des Projekts
  40. ­­­­­­­­­­­­­­­­­­­
  41. Das komplette Projekt "Patterns" beinhaltet folgende Dateien:
  42.  
  43. * Patterns.dok          Diese Dokumentation
  44. * Patterns.def          Quelltext der Definition
  45. * Patterns.mod          Quelltext der Implementation
  46. * TestPatterns.mod      Quelltext des Demoprogramms
  47. * TestPatterns          Ausführbare Demo
  48.  
  49. (Stand 02.Jan.1990)
  50.  
  51.  
  52. Beschreibung
  53. ­­­­­­­­­­­­
  54.  
  55. Das Modul exportiert eine Prozedur, die prüft, ob ein String (z.B.
  56. Dateiname) auf ein bestimmtes Muster paßt. Dabei wird Groß- und
  57. Kleinschreibung unterschieden. Ist dies nicht erwünscht, müssen alle
  58. Buchstaben des zu testenden Strings UND des Musters in Großbuchstaben
  59. gewandelt werden (z.B. mit Str.CapString).
  60. Die derzeitige Version beherrscht lediglich folgende Jokerzeichen:
  61.  
  62.  "?": steht für ein beliebiges Zeichen
  63.  "*": steht für eine Folge von 0 oder mehr beliebigen Zeichen
  64.  
  65. Dies entspricht nicht den AmigaDos- oder ARP-Befehlen, die auch Klammerung,
  66. Alternativen ("|") und Wiederholungen ("#") zulassen, ist aber in den
  67. meisten Fällen ausreichend. Die Joker dürfen ohne Einschränkungen auch
  68. beliebig gemischt verwendet werden.
  69.  
  70. Beispiele:
  71.  
  72.  Muster:        paßt auf:
  73.  
  74.  *              alles
  75.  ????           alle Strings mit 4 Zeichen
  76.  ???*           alle Strings mit 3 oder mehr Zeichen
  77.  *.info         alle Strings mit der Endung ".info"
  78.  *x*            alle Strings die mindestens ein "x" enthalten
  79.  *x*x*          alle Strings die mindestens zwei "x" enthalten
  80.  *x?*x*         wie oben, mit der Einschränkung, daß ein Zeichen Abstand
  81.                 dazwischen sein muß
  82.  ???.*          alle Strings mit 3 Zeichen und einer beliebigen Endung
  83.                 beginnend mit "."
  84.  *???.def       alle Strings mit 3 oder mehr Zeichen und der Endung ".def"
  85.  
  86. Die Überprüfung erfolgt übrigens mit einem Backtracking-Algorithmus, auch
  87. wenn dies nicht sofort erkennbar ist. Das Backtracking steckt in der
  88. doppelten Rekursion im folgenden boolschen Ausdruck in der Prozedur Test:
  89.  
  90.         |"*":
  91.           RETURN Test (PatPos + 1, StrPos) OR
  92.                  (StrPos < MaxStr) AND Test (PatPos, StrPos + 1)
  93.  
  94. (doppelt rekursiv, weil die Prozedur sich zweimal selbst aufruft). Man
  95. beachte, daß die zweite Rekursion dabei jedoch nur auftritt, wenn die erste
  96. nicht erfolgreich war. Das zweite Argument eines boolschen "OR"-Ausdrucks
  97. wird nämlich nur ausgewertet, wenn das erste FALSE ist, während das zweite
  98. Argument eines boolschen "AND"-Ausdrucks nur ausgewertet wird, wenn das
  99. erste TRUE ist.
  100.  
  101. Alles logo ?!?!
  102.  
  103. Zur Veranschaulichung ein Beispiel:
  104.  
  105.  Muster:        String:
  106.  
  107.  *TEST*         PATTERNTEST.MOD
  108.  
  109. Würde man lediglich Zeichen für Zeichen nacheinander prüfen, würde das "TE"
  110. des Musters bereits auf das "TE" von "PATTERN" passen. Dies führt jedoch in
  111. eine Sackgasse, da das folgende "S" des Musters nicht auf das "R" von
  112. "PATTERN" paßt.
  113. Jetzt könnte jemand sagen: Wo liegt das Problem? Man braucht doch nur mit
  114. der Prozedur Strings.Occurs nach "TEST" zu suchen!
  115. Aber was macht man, wenn das Muster "TE?T" lautet. Ok, man könnte sich eine
  116. Suchprozedur schreiben, die das "?" berücksichtigt, aber dann artet das
  117. ganze doch extrem ins Komplizierte aus. Im Prinzip programmiert man dann
  118. nichts anderes als ein iteratives Backtracking, und das ist bekanntlich
  119. kompliziert und unübersichtlich.
  120.  
  121. Theoretisch könnte man die Prozedur noch optimieren, indem man die
  122. sogenannte "tail recursion", also Rekursion am Ende der Prozedur
  123. eliminiert. Da das ganze dann aber noch schwieriger zu durschauen wäre,
  124. überlasse ich dies jenen Leuten, die meinen, sich wegen 50ns
  125. Geschwindigkeitsvorteil einen Fuß ausreißen zu müssen.
  126.  
  127.  
  128. Demo- / Testprogramm
  129. ­­­­­­­­­­­­­­­­­­­­
  130. Das Programm "TestPatterns" ist eine einfache Demo für die Benutzung von
  131. Patterns. Es erlaubt die Eingabe eines Musters und beliebig vieler Strings,
  132. die mit dem Muster verglichen werden. Beendet wird die Demo mit der eingabe
  133. eines leeren Strings, der übrigens auch noch mit dem Muster verglichen
  134. wird. Vorsicht mit Strings, die Leerzeichen enthalten (liegt an
  135. ReadString() )!
  136.  
  137.  
  138. Zum Schluß...
  139. ­­­­­­­­­­­­­
  140. noch eine Anmerkung: Angeblich soll es jemand geschafft haben, eine
  141. Patternmatching-Prozedur zu schreiben, die unendlich viel UMSTÄNDLICHR,
  142. UNÜBERSICHTLICHER und LÄNGER ist, als die hier beschriebene und zu allem
  143. Überfluß auch noch die EINSCHRÄNKUNG hat, Wildcards NUR am ANFANG oder am
  144. ENDE des Musters zu erlauben. Gerüchten zufolge, soll derjenige es sogar
  145. geschafft haben, daß sein Programm, in dem diese Prozedur enthalten ist,
  146. auf einer der letzten Amok-Disks veröffentlicht wurde. Mein Rat: Kaufen Sie
  147. sich einen Strick und erschießen Sie sich, wo das Wasser am tiefsten ist.
  148.  
  149.  
  150.